package com.huangyi;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 为高尔夫比赛砍树
        Solution solution1 = new Solution();
        System.out.println("为高尔夫比赛砍树:");
        List<List<Integer>> forest1 = Arrays.asList(
            Arrays.asList(1, 2, 3),
            Arrays.asList(0, 0, 4),
            Arrays.asList(7, 6, 5)
        );
        System.out.println("forest=[[1,2,3],[0,0,4],[7,6,5]]: " + solution1.cutOffTree(forest1)); // 6

        // 测试用例 - 矩阵
        Solution2 solution2 = new Solution2();
        System.out.println("\n01矩阵:");
        int[][] mat1 = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        int[][] result1 = solution2.updateMatrix(mat1);
        System.out.print("mat=[[0,0,0],[0,1,0],[0,0,0]]: ");
        printMatrix(result1);

        int[][] mat2 = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
        int[][] result2 = solution2.updateMatrix(mat2);
        System.out.print("mat=[[0,0,0],[0,1,0],[1,1,1]]: ");
        printMatrix(result2);
    }

    // 辅助方法：打印矩阵
    static void printMatrix(int[][] mat) {
        System.out.print("[");
        for (int i = 0; i < mat.length; i++) {
            System.out.print("[");
            for (int j = 0; j < mat[i].length; j++) {
                System.out.print(mat[i][j]);
                if (j < mat[i].length - 1) System.out.print(",");
            }
            System.out.print("]");
            if (i < mat.length - 1) System.out.print(",");
        }
        System.out.println("]");
    }

    // 为高尔夫比赛砍树
    static class Solution {
        // 定义方向数组：上下左右四个方向
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};
        int m, n;

        public int cutOffTree(List<List<Integer>> forest) {
            m = forest.size();
            n = forest.get(0).size();
            int result = 0;
            int si = 0, sj = 0;

            // 获取树：收集所有高度>1的单元格
            // 新数组列表与原数字建立映射
            List<int[]> listNum = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int h = forest.get(i).get(j);
                    if (h > 1) listNum.add(new int[]{h, i, j});
                }
            }

            // 树排序：按高度升序
            listNum.sort(Comparator.comparingInt(a -> a[0]));

            // 进行遍历
            // si, sj 表示当前要进行 bfs 的格子坐标
            // ti, tj 表示要搜索的目标树坐标
            for (int[] t : listNum) {
                int ti = t[1], tj = t[2];
                // 因为要从 forest 拿值, 所以方法需要传入 forest
                int tmp = bfs(forest, si, sj, ti, tj);
                // 因为0是有效值, 所以判断的时候使用-1来标记违法值
                if (tmp == -1) return -1;
                result += tmp;
                // 赋值到刚查到的最小树, 才能实现最少步骤完成任务
                si = ti;
                sj = tj;
            }
            return result;
        }

        // BFS 求两点最短路
        public int bfs(List<List<Integer>> forest, int si, int sj, int ti, int tj) {
            // 如果起点和终点相同, 不用走
            if (si == ti && sj == tj) return 0;

            // 用于标记每一次遍历的监察数据, 涉及到多次调用不能污染 vis
            boolean[][] vis = new boolean[m][n];
            // 用于存储当前 si, sj 所代表的要进行 bfs 遍历的格子
            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[]{si, sj});
            vis[si][sj] = true;

            int step = 0;

            while (!q.isEmpty()) {
                int size = q.size();
                // 按层进行划分
                for (int i = 0; i < size; i++) {
                    int[] num = q.poll();
                    int a = num[0], b = num[1];
                    // 如果到达目标坐标, 返回当前步数
                    if (a == ti && b == tj) return step;
                    for (int j = 0; j < 4; j++) {
                        int x = a + dx[j], y = b + dy[j];
                        // 边界内 + 非障碍 + 未访问 才能入队
                        if (x >= 0 && x < m && y >= 0 && y < n && forest.get(x).get(y) != 0 && !vis[x][y]) {
                            q.offer(new int[]{x, y});
                            vis[x][y] = true;
                        }
                    }
                }
                step++;
            }
            // 无法到达目标
            return -1;
        }
    }

    // 01矩阵
    static class Solution2 {
        int m, n;
        boolean[][] vis;
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};

        public int[][] updateMatrix(int[][] mat) {
            m = mat.length;
            n = mat[0].length;
            vis = new boolean[m][n];

            Queue<int[]> q = new LinkedList<>();

            // 多源入队：所有 0 作为起点，距离为 0，已访问
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (mat[i][j] == 0) {
                        q.offer(new int[]{i, j});
                        vis[i][j] = true;
                    }
                }
            }

            int step = 1; // 第一层邻居距离为 1
            while (!q.isEmpty()) {
                int size = q.size();
                // 分层遍历
                while (size-- != 0) {
                    int[] cur = q.poll();
                    int a = cur[0], b = cur[1];

                    // 扩展四邻
                    for (int k = 0; k < 4; k++) {
                        int x = a + dx[k], y = b + dy[k];
                        // 合法且未访问的邻居才入队，并设置距离
                        if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
                            q.offer(new int[]{x, y});
                            vis[x][y] = true;
                            mat[x][y] = step; // 到最近 0 的距离
                        }
                    }
                }
                step++; // 下一层的距离 +1
            }

            return mat;
        }
    }
}